package queue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 定义一个队列并实现函数 max_value 得到队列里的最大值
 */
public class MaxQueue {

  /**
   * 使用三个队列来进行实现
   */
  class MaxQueue1 {
    Queue<Integer> queue;
    Deque<Integer> maxQueue1;
    Deque<Integer> maxQueue2;


    public MaxQueue1() {
      queue = new LinkedList<>();
      maxQueue1 = new LinkedList<>();
      maxQueue2 = new LinkedList<>();
    }

    public int max_value() {
      return getValueFromMaxQueue();
    }

    public void push_back(int value) {
      queue.offer(value);
      if (maxQueue1.isEmpty() && maxQueue2.isEmpty()) {
        maxQueue1.offerLast(value);
      } else if (!maxQueue1.isEmpty() && maxQueue2.isEmpty()) {
        pushValueInMaxQueue(value, maxQueue1, maxQueue2);
      } else if (maxQueue1.isEmpty() && maxQueue1.isEmpty()) {
        pushValueInMaxQueue(value, maxQueue2, maxQueue1);
      }
    }

    /**
     * @param value
     * @param queue1 queu1不为空
     * @param queue2 queue2为空
     */
    public void pushValueInMaxQueue(int value, Deque<Integer> queue1, Deque<Integer> queue2) {
      if (value <= queue1.peekLast()) {
        queue1.offerLast(value);
      } else {
        while (!queue1.isEmpty()) {
          int tmp = queue1.pollLast();
          if (tmp <= value) {
            queue2.addFirst(value);
          } else {
            queue2.addFirst(tmp);
          }
        }
        queue2.addLast(value);
      }
    }

    public void deleteValueFromMaxQueue() {
      if (!maxQueue1.isEmpty() && maxQueue2.isEmpty()) {
        maxQueue1.pollFirst();
      } else if (maxQueue1.isEmpty() && !maxQueue2.isEmpty()) {
        maxQueue2.pollFirst();
      }
    }

    public int getValueFromMaxQueue() {
      if (maxQueue1.isEmpty() && maxQueue2.isEmpty()) {
        return -1;
      } else if (!maxQueue1.isEmpty() && maxQueue2.isEmpty()) {
        return maxQueue1.peekFirst();
      } else if (maxQueue1.isEmpty() && !maxQueue2.isEmpty()) {
        return maxQueue2.peekFirst();
      }
      return -1;
    }

    public int pop_front() {
      if (!queue.isEmpty()) {
        deleteValueFromMaxQueue();
        return queue.poll();
      } else {
        return -1;
      }
    }
  }

  /**
   * 优化版
   */
  class MaxQueue2 {
    Queue<Integer> queue;
    Deque<Integer> maxQueue;

    public MaxQueue2() {
      queue = new LinkedList<Integer>();
      maxQueue = new LinkedList<Integer>();
    }

    public int max_value() {
      if (maxQueue.isEmpty()) {
        return -1;
      }
      return maxQueue.peekFirst();
    }

    public void push_back(int value) {
      while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
        maxQueue.pollLast();
      }
      maxQueue.offerLast(value);
      queue.offer(value);
    }

    public int pop_front() {
      if (queue.isEmpty()) {
        return -1;
      }
      int ans = queue.poll();
      if (ans == maxQueue.peekFirst()) {
        maxQueue.pollFirst();
      }
      return ans;
    }
  }
}

